package 回溯;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author aodre , QQ : 480029069
 * @date 2022/12/16 11:38
 */
public class leetcode139单词拆分I {



    /*
    超时
    但是 注意 这个 回溯的 写法
    我这个回溯 是只要 找到  一种 满足 的情况 就返回 true， 就不往下找了
     */
    public boolean solution(String s, List<String> wordDict){

        Set<String> set = new HashSet<>();
        for(String str : wordDict)
            set.add(str);


        return recursion(0,s,set,s.length());
    }
    public boolean recursion(int index,String s,Set<String> dict,int len) {
        if(index == len)
            return true;

        for(int i = index + 1 ;i <= len;i++){
            if(dict.contains(s.substring(index,i)) && recursion(i,s,dict,len)) {
                return true;
            }
                /*
                这样写 是正确的
                但是 上面的写法 会 更 简洁一些
                          boolean flag =  recursion(i,s,dict,len);
                if(flag)
                    return true;
            ***********
            但是 这样写 就是错的
            直接 return reucrsion（i，s，dict，len）；
            这样考虑的就太片面了！
                 */
        }
        return false;
    }


    /*
    dp
     */
    public static boolean dp(String s,List<String> dict){
        int len = s.length();
        Set<String> set = new HashSet<>();
        for(String str : dict)
            set.add(str);
        boolean dp[] = new boolean[len + 1];
        dp[len] = true;
        for(int index = len -1;index >= 0;index-- ){
            for(int i = index +1;i <= len;i++) {
                if (set.contains(s.substring(index, i)) && dp[i]) {
                    dp[index] = dp[i];
                    /*
                    为什么 break ，跟这道题有关系，因为 只要找到 一个 ，就行了
                    所以  ，这里可以break
                    如果这个题 换一种问法的话，那就有所不同了
                     */
                    break;
                }
            }
//            dp[index] = false; 可以直接省略，因为 本来就是false
        }
        return dp[0];
    }


    /*
      用记忆化搜素 也可以
      这样的 话 就需要 记录的
      就不能是一种情况了，需要 满足的 情况 全部记忆
     */
    public boolean solutionOne(String s, List<String> wordDict){
        int len = s.length();
        Set<String> set = new HashSet<>();
        for(String str : wordDict)
            set.add(str);
        int dp[] = new int[len + 1];

//        Arrays.fill(dp,-1);
        return recursionOne(0,s,set,s.length(),dp);
    }
    public boolean recursionOne(int index,String s,Set<String> dict,int len,int dp[]) {
        if(index == len){
//            dp[index] = 1;
            return true;
        }
        /*
        记忆化搜索，的关键，是 算过的 子过程直接返回，没算过的 去算，
        关键是， 怎么去 区分 算过还是没有算过 ，这件 事情上面，
        要有一个区分的 设计
         */
        if(dp[index] != 0)
            return dp[index] == 1 ;//? true : false;

        for(int i = index + 1 ;i <= len;i++){
            if(dict.contains(s.substring(index,i)) && recursionOne(i,s,dict,len,dp)){
                    dp[index] = 1;
                    return true;
            }
        }
        dp[index] = - 1;
        return false;
    }






    public static void main(String[] args) {
        String s = "catsanddog";
        List<String> dict = Arrays.asList("cats","dog","sand","and","cat");
        boolean dp = dp(s, dict);
        System.out.println(dp);
        String str[] = {"cats","dog","sand","and","cat"};
        System.out.println(Arrays.toString(solution(s,str)));
    }

    /*
    对该题 就行，变种,: 把当前的 单词 拆分成 存在 于 wordDict 的 的方案 有几种
    这就是 熟悉的 那种 动态规划的味道了！
    用记忆化搜索来实现一下；
    在 练习的 时候 ，记忆化搜索和动态规划都写
    在 笔试的 时候，优先 记忆化搜索，如果 存在 斜率优化 或者 四边形不等式的 话，
    改成 dp
     */

    public static int[] solution(String s,String [] wordDict){
        Set<String> set = new HashSet<>();
        for(String str : wordDict)
            set.add(str);
        int len  = s.length();
        int dp [] = new int[len + 1];
        // 因为  0 的存在 会干扰 ，到底当前 子过程算没算过
        Arrays.fill(dp,- 1);
        return new int [] {recursionMem(0,s,set,len),recursionMem(0,s,set,len,dp)};
    }
    public static int recursionMem(int index,String s,Set<String> dict,int len){
        if(index == len)
            return 1;
        int ans = 0;
        for(int  i = index + 1;i <= len;i++){
            if(dict.contains(s.substring(index,i)))
                ans += recursionMem(i,s,dict,len);
        }
        return ans;
    }
    public static int recursionMem(int index,String s,Set<String> dict,int len,int dp[]){
        if(index == len)
            return 1;
        if(dp[index] != -1)
            return dp[index];
        int ans = 0;
        for(int  i = index + 1;i <= len;i++){
            if(dict.contains(s.substring(index,i)))
                ans += recursionMem(i,s,dict,len);
        }
//        dp[index] = ans;
        return dp[index] = ans;
    }

    /*
     这种 coding 真的是 美如画
     beat 100 %
     */
    class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            return doWordBreak(s, 0, wordDict, new boolean[s.length()]);
        }
        private boolean doWordBreak(String s, int offset, List<String> dict, boolean[] remo) {
            if (s.length() == offset) return true;
            if (remo[offset]) return false;
            for (String word : dict) {
                if (!s.startsWith(word, offset)) continue;
                if (doWordBreak(s, offset + word.length(), dict, remo)) return true;
            }
            remo[offset] = true;
            return false;
        }
    }

    /*
    上面这个 和下面这个 知识提供 一种新的 思维方式
    ，知道 还可以这样的 去写的方式！
    不同的 思维发散能力
     */
    class SolutionOne {
        public boolean wordBreak(String s, List<String> wordDict) {
            Set<String> set =new HashSet<>(wordDict);
            int minLength=wordDict.get(0).length();
            int maxLength=wordDict.get(0).length();
            for(String item:wordDict){
                minLength=Math.min(minLength,item.length());
                maxLength=Math.max(maxLength,item.length());

            }
            boolean[] dp = new boolean[s.length()+1];
            dp[0]=true;

            for(int i=1;i<=s.length();i++){
                for(int j=Math.max(0,i-maxLength);j<=i-minLength;j++){
                    if(dp[j]&&set.contains(s.substring(j,i))){
                        dp[i]=true;
                        break;
                    }
                }
            }
            return dp[s.length()];
        }
    }
}
